package com.mj;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import com.mj.printer.BinaryTreeInfo;

@SuppressWarnings({ "unused", "rawtypes" })
public class BinarySearchTree<E> implements BinaryTreeInfo {
	private int size;
	private Node<E> root;
	private Comparator<E> comparator;
	private int i;
		
	public BinarySearchTree() {
		this(null);
	}

	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}

	public int size() {
		return size;
	}
	
	public Node<E> getbstRoot() {
		return root;
	}
	
	public boolean isEmpty() {
		return size == 0;
	}
	
	public void clear() {
		
	}
	
	@SuppressWarnings("null")
	public void add(E element) {
		elementNotNullCheck(element);
		if (root == null) {
			root = new Node<>(element, null);
			size++;
			return;
		}
		Node<E> node = root;
		Node<E> parent = null;
		int cmp = 0;
		while (node != null) {
			 cmp = compare(element,node.element);
			 parent = node;
			if (cmp > 0) {
				node = node.right;
			}else if (cmp < 0) {
				node = node.left;
			}else {
				return;
			}
		}
		Node<E> newNode = new Node<>(element, parent);
		if (cmp > 0) {
			parent.right = newNode;
		}else {
			parent.left = newNode;
		}
		size++;
	}
	
	public void remove(E element) {
		remove(node(element));
	}
	
	private void remove(Node<E> node) {
		if (node == null) {
			return;
		}
		size--;
		
		if (node.hasTwoChildren()) {
			Node<E> p = successor(node);
			node.element = p.element;
			node = p;
		}
		
		Node<E> replacement = node.left != null ? node.left : node.right;
		if (replacement != null) {
			if (node.parent == null) {
				root = replacement;
				replacement.parent = null;
			}else if (replacement.parent == node.parent.left) {
				node.parent.left = replacement;
			}else if (replacement.parent == node.parent.right) {
				node.parent.right = replacement;
			}
		}else {
			if (node.parent == null) {
				root = null;
			}
			else if (node.parent.left == node) {
				node.parent.left = null;
			}else if (node.parent.right == node) {
				node.parent.right = null;
			}
		}
	}
	
	private Node<E> node(E element) {
		Node<E> node = root;
		while (node != null) {
			int cmp = compare(element, node.element);
			if (cmp == 0) {
				return node;
			}else if (cmp > 0) {
				node = node.right;
			}else {
				node = node.left;
			}
		}
		return null;
	}
	
	public boolean contains(E element) {
		return false;
	}
	
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
    
    @SuppressWarnings("unchecked")
	private int compare(E e1, E e2) {
    	if (comparator == null) {
    		return ((Comparable<E>)e1).compareTo(e2);
		}
		return comparator.compare(e1, e2);
	}
    
//    public void inorderTraversal() {
//		inorderTraversal(root);
//	}
    
//    public void inorderTraversal(Node<E> node) {
//		if (node == null) {
//			return;
//		}
//		inorderTraversal(node.left);
//		System.out.println(node.element);
//		inorderTraversal(node.right);
//	}
    
//    public void postorderTraversal() {
// 		postorderTraversal(root);
// 	}
//    
//  public void postorderTraversal(Node<E> node) {
//		if (node == null) {
//			return;
//		}
//		postorderTraversal(node.left);
//		postorderTraversal(node.right);
//		System.out.println(node.element);
//	}
    
    public void levelorderTraversal(Visitor<E> visitor) {
    	levelorderTraversal(root,visitor);
 	}
    
    public void levelorderTraversal(Node<E> root,Visitor<E> visitor) {
    	Queue<Node<E>> queue = new LinkedList<>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {
		  Node<E> node = queue.poll();
		  if (visitor.visit(node.element)) {
			  break;
		  }
		  if (node.left != null) {
			queue.offer(node.left);
		  }
		  if (node.right != null) {
			queue.offer(node.right);
		  }
		}
    }
        
    public void postorderTraversal() {
 		postorderTraversal(root);
 	}
    
    public void postorderTraversal(Node<E> node) {
		Stack<Node<E>>stack = new Stack<>();
		Node<E> curNode = node;
		Node<E> preNode = null;
		while (curNode != null || !stack.isEmpty()) {
			while (curNode != null) {
				stack.push(curNode);
				curNode = curNode.left;
			}
			curNode = stack.pop();
			if (curNode.right == null || curNode.right == preNode) {
				System.out.println(curNode.element);
				preNode = curNode;
				curNode = null;
			}else {
				stack.push(curNode);
				curNode = curNode.right;
			}
		}
    }
    
    
    public void inorderTraversal() {
 		inorderTraversal1(root);
 	}
    
    public void inorderTraversal(Node<E> node) {
		Stack<Node<E>> stack = new Stack<>();
		while (!stack.isEmpty() || node != null) {
			if (node != null) {
				stack.push(node);
				node = node.left;
			}else{
				Node<E> tmpNode = stack.pop();
				System.out.println(tmpNode.element);
				node = tmpNode.right;
			}
		}
    }
    
    public void inorderTraversal1(Node<E> root) {
		Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        root = root.left;
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                stack.push(root);
                root = root.left;
            }else {
                Node<E> node = stack.pop();
				System.out.println(node.element);
                root = node.right;
            }
        }
    }
    
    
    public List<E> inorderTraversal2() {
        if (root == null) {
            return new ArrayList<>();
        }

        Node<E> cur = root;    // 记录当前节点位置
        List<E> res = new ArrayList<>();
        while (cur != null) {
            if (cur.left == null) {   // 左节点为空，移到右子节点
                res.add(cur.element);
                cur = cur.right;
            }  else {
                Node<E> prev = cur.left;
                if (prev.right == cur) {
                    System.out.println();
				}
                while (prev.right != null && prev.right != cur) { // 遍历到左子树的最右侧节点
                    prev = prev.right;
                }
                if (prev.right == null) {        // 建立返回父节点连接
                    prev.right = cur;
                    cur = cur.left;
                } else {                        // 左子树建立了连接，说明遍历完了，可以拆除连接
                    res.add(cur.element);           // 中序遍历录入当前节点
                    prev.right = null;
                    cur = cur.right;
                }
            }
        }
        return res;
    }

    
    
    
    public List<List<E>> levelOrder() {
    	return levelOrder(root);
    }
    
    public List<List<E>> levelOrder(Node<E> root) {
        List<List<E>> ret = new ArrayList<List<E>>();
        if (root == null) {
            return ret;
        }

        Queue<Node<E>> queue = new LinkedList<Node<E>>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<E> level = new ArrayList<E>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                Node<E> node = queue.poll();
                level.add(node.element);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
    
    
//    public ArrayList<ArrayList<E>> levelOrder(Node<E> root) {
//    	ArrayList<ArrayList<E>> list = new ArrayList<>();
//		Queue<Node<E>> queue = new LinkedList<>();
//    	if (root == null) {
//			return list;
//		}
//    	queue.offer(root);
//    	int levelSize = 1;
//    	ArrayList<E> levelList = new ArrayList<>();
//    	
//    	while (!queue.isEmpty()) {
//    		Node<E> node = queue.poll();
//    		System.out.println(node.element);
//
//			levelList.add(node.element);
//			levelSize --;
//			if (node.left != null) {
//				queue.offer(node.left);
//			}
//			if (node.right != null) {
//				queue.offer(node.right);
//			}
//			if (levelSize == 0) {
//				levelSize = queue.size();
//				list.add(levelList);
//				levelList.clear();
//				System.out.println(levelList);
//			}
//		}
//    	return list;
//    }

    
//    public void preorderTraversal() {
//		Stack<Node<E>> stack = new Stack<>();
//		if (root == null) return;
//		stack.push(root);
//		while (!stack.isEmpty()) {
//			Node<E> node = stack.pop();
//			System.out.print(node.element);
//			System.out.print(",");
//			if (node.right != null) {
//				stack.push(node.right);
//			}
//			if (node.left != null) {
//				stack.push(node.left);
//			}
//		}
//	}
    
    public  static abstract class  Visitor<E> {
        public	boolean stop;
    	public abstract	boolean visit(E element);
    }
 
//    /// 前序遍历
//    public void preorderTraversal(Visitor<E> visitor) {
//    	preorderTraversal(root,visitor);
//	}
//    
//    private void preorderTraversal(Node<E> node,Visitor<E> visitor) {
//		if (node == null || visitor.stop == true) {
//			return;
//		}
//		visitor.stop  = visitor.visit(node.element);
//		preorderTraversal(node.left,visitor);
//		preorderTraversal(node.right,visitor);
//	}
    
    public Node<E> predecessor(Node<E> node) {
    	if (node == null) {
			return null;
		}
    	Node<E> p = node.left;
    	if (p != null) {
			while (p.right != null) {
				p = p.right;
			}
			return p;
		}
    	while (node.parent != null && node == node.parent.left) {
			node = node.parent;
		}
    	return node.parent;
	}
    
    public Node<E> successor(Node<E> node) {
		if (node == null) {
			return null;
		}
		Node<E> p = node.left;
		if (p != null) {
			while (p.right != null) {
				p= p.right;
			}
			return p;
		}
		
		while (node.parent != null && node == node.parent.right) {
			node = node.parent;
		}
		
		return node.parent;
	}
    
    public void preorderTraversal() {
		preorderTraversal(root);
	}
    
    public void preorderTraversal(Node<E> root) {
    	if (root == null) {
			return;
		}
    	ArrayList<E> list = new ArrayList<>();
    	Stack<Node<E>> stack = new Stack<>();
    	stack.push(root);
    	while (!stack.isEmpty()) {
			Node<E> node = stack.pop();
			list.add(node.element);
			System.out.println(node.element);
			if (node.right != null) {
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}
	}
    
    public Node<E> invertTree() {
    	return invertTreeTraversal(root);
	}
    
    public Node<E> invertTreeTraversal(Node<E> root) {
    	if (root == null) {
			return null;
		}
    	Node<E> tmp = root.right;
    	root.right = root.left;
    	root.left = tmp;
		invertTreeTraversal(root.left);
		invertTreeTraversal(root.right);
		return root;
	}
    
	public static class Node<E> {
		public E element;
		public Node<E> left;
		public Node<E> right;
		public Node<E> parent;
		public Node(E element, Node<E> parent) {
			this.element = element;
			this.parent = parent;
		}
		
		public boolean isLeaf() {
			return left == null && right == null;
		}
		
		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		toString(root, sb, "");
		return sb.toString();
	}
	
	private void toString(Node<E> node, StringBuilder sb, String prefix) {
		if (node == null) return;

		toString(node.left, sb, prefix + "L---");
		sb.append(prefix).append(node.element).append("\n");
		toString(node.right, sb, prefix + "R---");
	}
	
	public boolean isComplete() {
		Queue<Node<E>> queue = new LinkedList<>();
		queue.offer(root);
		boolean isleaf = false;
		while (!queue.isEmpty()) {
			Node<E> node = queue.poll();
			if (isleaf && !node.isLeaf()) return false;
			if (node.right != null) {
				queue.offer(node.right);
			}else if (node.right != null && node.left == null) {
				return false;
			}
			if (node.left != null) {
				queue.offer(node.left);
			}else {
				isleaf = true;
			}
 		}
		return true;
	}
	
	public int height() {
		int levelSize = 1;
		int height = 0;
		Queue<Node<E>> queue = new LinkedList<>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {
		  Node<E> node = queue.poll();
		  levelSize--;
		  if (node.left != null) {
			queue.offer(node.left);
		  }
		  if (node.right != null) {
			queue.offer(node.right);
		  }
		  if (levelSize == 0) {
			height ++;
			levelSize = queue.size();
		  }
		}
		return height;
	}
	
//	public int height() {
//		return height(root);
//	}
//	
//	public int height(Node<E> node) {
//		if (node == null) {
//			return 0;
//		}
//		return 1 + Math.max(height(node.right), height(node.left));
//	}

	@Override
	public Object root() {
		// TODO Auto-generated method stub
		return root;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object left(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).left;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object right(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).right;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object string(Object node) {
		// TODO Auto-generated method stub
		return ((Node<E>)node).element;
	}
}
